package lc.q300_350;

import java.util.*;

/**
 * 给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。
 *
 */
public class Q315 {

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> counts = new ArrayList<>(nums.length);
        // 暴力解法，超时
        for (int i = 0; i < nums.length; i++) {
            int count  = 0;
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i] < nums[j]) {
                    count ++;
                }
            }
            counts.add(count);
        }
        return counts;
    }

    private int[] sortNums;
    private int[] counts;

    public void init(int length) {
        counts = new int[length];
    }

    public int  lowBit(int x) {
        return x & (-x);
    }

    public int query(int pos) {
        // 查询前缀和
        int ret  = 0;
        while (pos > 0) {
            ret += counts[pos];
            pos -= lowBit(pos);
        }
        return ret;
    }

    public void update(int pos) {
        while (pos < counts.length) {
            counts[pos] += 1;
            pos += lowBit(pos);
        }
    }

    public int getId(int x) {
        return Arrays.binarySearch(sortNums, x) + 1;
    }

    public void sortNums(int[] nums) {
        Set<Integer> set = new HashSet<>(nums.length);
        for (int num : nums) {
            set.add(num);
        }
        sortNums = set.stream().sorted().mapToInt(Integer::intValue)
                .toArray();
    }

    public List<Integer> countSmaller2(int[] nums) {
        List<Integer> resultList = new ArrayList<>();
        // 采用树状数组
        // 树状数组针对符合以下条件的场景
        // 1. 需要计算前缀和
        // 2. 需要更新数组
        // 3. 不断重复以上操作
        // 正常情况下，计算前缀和的N次操作算法复杂度时O(N^2),更新数组的复杂度时O(N）
        // 添加前缀和辅助数组的情况下，N次操作算法计算前缀和的复杂度时O(N）,但是更新操作退化回了O(N^2)
        // 这个时候就采取树状数组的方式
        // 树状数组就是通过将1.2操作都优化成O(NLogN）
        // 首先使用一个辅助数组，这个数组有以下特点
        // C1 = A1
        // C2 = A2 + C1
        // C3 = A3
        // C4 = A4 + C2 + C3
        // C5 = A5
        // C6 = C5 + A6
        // C7 = A7
        // C8 = A8 + C7 +
        init(nums.length);
        sortNums(nums);
        for (int i = nums.length - 1; i >= 0; i--) {
            // 获取nums[i]在排序后的位置
            int id = getId(nums[i]);
            resultList.add(query(id - 1));
            update(id);
        }
        Collections.reverse(resultList);
        return resultList;
    }

    public static void main(String[] args) {
        final Q315 q315 = new Q315();
        final List<Integer> list = q315.countSmaller2(new int[]{5, 2, 6, 1});
        System.out.println(list);
    }



}
